Network optimization has always been an important part of the business of building and upgrading communication networks. In a capacity deployment scenario, the network operator would like to minimize capital and operating expenses, while satisfying capacity and quality of service requirements. Capacity recovery services take the complementary approach of performing network optimization as part of the maintenance of an existing communication network. Here, the capital infrastructure is constrained, and the goal is to increase, and preferably maximize, the communication capacity and quality of service within the existing network.
On the face of it, capacity recovery and capacity deployment services could be seen as competing, since a successful capacity recovery service could postpone a network provider's need for new equipment. However, they should more properly be seen as complementary and synergistic. Capacity recovery provides a beneficial service to network providers who are unable or unwilling to make significant capital purchases. Common optimization tools and expertise can be applied for capacity recovery and capacity deployment, increasing the customers' confidence that they are receiving the greatest possible return on their capital and operational investment.
Network optimization can be performed network-wide, or with respect to a particular central office (CO) in the network. In a theoretical CO, a single switch is used to route information flows that pass between or among external trunks linking the CO to the remainder of a communication network. In a real CO, however, the number of trunks and the aggregate traffic load are often higher than the capacity of any single switch. Thus, the CO must contain multiple switches coupled to one another by internal trunks. The multiple switches in a particular CO are collectively termed a “switching center.”
If the traffic patterns are dynamic and unpredictable, multiple switches can be arranged into non-blocking configurations capable of handling arbitrary permutations of demands. In many cases however, the aggregate flows between external trunks are static, or are expected to satisfy fairly tight static bounds. In such cases, it is sufficient and much less expensive to design the configuration of a CO only to satisfy a given static demand pattern.
Although geography and rights of way constrain the physical configuration of a wide area communication network and therefore make it expensive to change, the internal configuration of a CO may be designed relatively freely and inexpensively. Thus, the configuration of a CO can be the subject of optimization. The CO configuration problem may have a number of optimization objectives, including capital expenses, operating expenses and “switching load” (which is the total amount of traffic observed by all switches in a given CO). Of these, switching load has historically received the least attention.
Switching load has two components: fundamental load, which is the set of flows between external trunks, and overhead, which is twice the sum of all traffic flowing between local switches on internal trunks. Reducing the overhead almost certainly reduces the cost of equipment required.
A very simple form of this problem is equivalent to the well known “min k-cut” problem in graph theory. Suppose that a given CO has N external trunks, that ti,j>0 represents the aggregate demand between trunks i and j, and that the CO should use k switches. The task is to assign trunks having as much traffic as possible in common onto the same switch such that the flow between the switches is minimized. According to the min k-cut problem, the trunks are identified with the vertices of a fully connected graph, where a cost ti,j is associated with edge (i,j). The min k-cut problem seeks to cut the graph into k parts, in such a way that the total weight of the edges in the cut is minimized. Unfortunately, the min k-cut problem is NP-hard with respect to k and N, making it impractical for analyzing most real COs.
If k is fixed, it is polynomial in N (see, e.g., Goldschmidt, et al., “A Polynomial Algorithm for the Kappa-Cut Problem for Fixed Kappa,” Mathematics of Operations Research, (1994), pp. 24-37, incorporated herein by reference). Relatively simple 2-approximations to the problem for fixed k exist (see, e.g., Saran, et al., “Finding k-cuts Within Twice the Optimal,” SIAM J. Computing, (1995), pp. 101-108, incorporated herein by reference). Unfortunately, the known 2-approximations leave out switch constraints, which are the very reason that a CO needs multiple switches in the first place.
The simplest useful constraint is to limit the number of trunks that can be assigned to any switch, or equivalently to limit the cardinality of the connected components of the k-cut. A relatively efficient “swap” heuristic for this problem was developed in Kernighan, et al., “An Efficient Heuristic for Partitioning Graphs,” Bell Systems Tech. J. (1970), pp. 291-308, incorporated herein by reference. Unfortunately, limiting the number of trunks that can be assigned to a switch is only one of many constraints that may be encountered in deciding upon the proper configuration of a CO, which limits the the utility of Kernighan's heuristic.
What is needed in the art is a system for improving the configuration of a switching center. The system could be used to design new networks, avoiding under- or over-engineering the network. Ignoring the overheads that necessarily arise for internal trunks would lead to optimistic estimates of cost and switching load. On the other hand, in the absence of an optimization system, a tendency exists to make overly conservative estimates using rules of thumb. Secondly, the system could be used to improve the performance of existing switching centers as part of a capacity recovery effort. If the degree of improvement is sufficient, the changes would be economically justified. What is further needed in the art is a method for reducing switching overhead in a CO of a communication network.